/*
ACboy needs your help
ACboy has N courses this term, and he plans to spend at most M days on study.Of course,the profit he will gain from different course depending on the days he spend on it.How to arrange the M days for the N courses to maximize the profit?
Input
The input consists of multiple data sets. A data set starts with a line containing two positive integers N and M, N is the number of courses, M is the days ACboy has.
Next follow a matrix Aiijj, (1<=i<=N<=100,1<=j<=M<=100).Aiijj indicates if ACboy spend j days on ith course he will get profit of value Aiijj.
N = 0 and M = 0 ends the input.
Output
For each data set, your program should output a line which contains the number of the max profit ACboy will gain.
Sample Input
2 2
1 2
1 3
2 2
2 1
2 1
2 3
3 2 1
3 2 1
0 0
Sample Output
3
4
6
题意：有n门课程和m天时间，完成a[i][j]得到的价值为第i行第j列的数字，求最大价值
思路：第n门课程，可以做一天，可以做两天，但他们排斥，做了一天，就不能再做一天，也就是不能再做这门课程。
*/
#include <bits/stdc++.h>
#define ll long long
#define PI acos(-1)
#define M(n, m) memset(n, m, sizeof(n));
const int INF = 1e9 + 7;
const int maxn = 1e5 + 100;
using namespace std;

int n, m, dp[maxn], a[111][111];

int main()
{
    while (scanf("%d%d", &n, &m) && n && m)
    {
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= m; j ++)
                scanf("%d", &a[i][j]);
        M(dp, 0)
        for (int i = 1; i <= n; i ++)
            for (int j = m; j >= 0; j --)
                for (int k = 0; k <= j; k ++)
                    dp[j] = max(dp[j], dp[j - k] + a[i][k]);
        printf("%d\n", dp[m]);
    }
    return 0;
}
